class Solution {
//    public int mySqrt(int x) {
//        if(x == 0){
//            return 0;
//        }else if (x < 4){
//            return 1;
//        }
////法一，遍历速度慢
////        for (long i = x/2; i>=2; i--){
////            if (i * i <= x){
////                return (int)i;
////            }
////        }
//
//        //法二，二分
//        long left = 2,right = x/2;
//        long mid;
//        while (left <= right){
//            mid = left + (right -left)/2;
//            if (left * left <= x && (left+1) * (left+1) > x){
//                return (int)left;
//            }
//            if (mid*mid <= x){
//                left = mid;
//            }else{
//                right = mid;
//            }
//        }
//        return 0;
//    }



    //二刷
    public int mySqrt(int x) {
        //法一：暴力
//        long left = 0;
//        while (left * left <= x){
//            left++;
//        }
//        return (int)--left;

        //法二：二分
//        if(x == 0){
//            return 0;
//        }else if (x < 4){
//            return 1;
//        }
//        //[ , )
//        long left = 0, right = x/2,mid;
//
//        while (left < right){
//            mid = (left+right)/2;
//            if( mid*mid <= x && (mid+1)*(mid+1) > x) return (int)mid;
//            else if (mid*mid > x) right = mid;
//            else if ((mid+1)*(mid+1) == x) return (int)(mid+1);
//            else if ((mid+1)*(mid+1) < x) left = mid+1;
//        }
//        return (int)left;

        long l = 0, r = x;

        while (l < r){
            long mid = (l + r)/2 + 1;
            if (mid * mid > x) r = mid - 1;
            else l = mid;
        }
        return (int)l;

    }





}